// Problem 233: Lattice points on a circle
// Let f(N) be the number of points with integer coordinates that are on a circle passing through (0,0), (N,0),(0,N), and (N,N).
// It can be shown that f(10000) = 36.
// What is the sum of all positive integers N ≤ 10^11 such that f(N) = 420 ?
// ----------
// https://mathworld.wolfram.com/SumofSquaresFunction.html
// To find in how many ways a positive integer n>1 can be expressed as a sum of k=2 squares ignoring order and signs, factor it as
// n =(2^a0)*(p1^2a1)*...*(pr^2ar)*(q1^b1)*...*(qs^bs), where the pi are primes of the form 4k+3 and the qi are primes of the form 4k+1.
// If n does not have such a representation with integer ai because one or more of the powers of pi is odd, then there are no representations.
// Otherwise, define B=(b1+1)(b2+1)...(br+1).
// r2(n)=0 if any ai is a half-integer.
// r2(n)=4*B if all ai is integer.
// -----------
// In this case, n=2N^2, then B=(2b1+1)(2b2+1)...(2br+1)
// 4*B=420, B=105=
// 1) 3*5*7=>exponent 1,2,3 or
// 2) 5*21=>exponent 2,10 or
// 3) 7*15=>exponent 3,7 or
// 4) 3*35=>1,17 X

// 简单说，寻找的数字特征是：由符合 (p % 4 = 1) 的质数的上述次幂和一个额外的 q（q的质因子 d 符合 d%4!=1）的乘积。

package main

import (
	"fmt"
	"projecteuler/euler"
)

var limit233 = 100000000000

func p233() {
	var ans int = 0
	euler.FillPrime(5000000)
	p := []int{}
	q := []int{}
	for _, v := range euler.PrimeList {
		if v%4 == 1 {
			p = append(p, v)
		} else {
			q = append(q, v)
		}
	}
	ps := getPpart(p)
	for _, v := range ps {
		check233(v, 0, q, &ans)
	}
	fmt.Println("Problem 233:", ans)
}
func getPpart(p []int) []int {
	result := []int{}
	for _, p1 := range p {
		if p1e7 := p1 * p1 * p1 * p1 * p1 * p1 * p1; p1e7 > limit233 {
			break
		} else {
			for _, p2 := range p {
				if p1 != p2 {
					temp1 := p1e7 * p1 * p1 * p1 * p2 * p2
					temp2 := p1e7 * p2 * p2 * p2
					if temp1 < limit233 {
						result = append(result, temp1)
					}
					if temp2 < limit233 {
						result = append(result, temp2)
					}
					if temp1 > limit233 && temp2 > limit233 {
						break
					}
				}
			}
		}
	}
	for _, p1 := range p {
		for _, p2 := range p {
			if p2*p2*p1 > limit233 {
				break
			}
			if p1 == p2 {
				continue
			}
			for _, p3 := range p {
				if p2*p2*p3*p3*p3 > limit233 {
					break
				}
				if p1 == p3 || p2 == p3 {
					continue
				}
				temp1 := p1 * p2 * p2 * p3 * p3 * p3
				if temp1 > limit233 {
					break
				}
				result = append(result, temp1)
			}
		}
	}
	return result
}

func check233(x, i int, q []int, ans *int) {
	*ans += x
	for j := i; j < len(q); j++ {
		if q[j]%4 != 1 {
			if x*q[j] > limit233 {
				break
			}
			check233(x*q[j], j, q, ans)
		}
	}
}
